﻿using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;

namespace PushBox
{
    class GameState
    {
        private GameState LastState { get; }

        public int Depth { get; protected set; }
        /// <summary>
        /// 游戏地图数组
        /// </summary>
        protected int[] Map { get; set; }

        public int Y { get; protected set; }

        public int X { get; protected set; }

        public int W { get; protected set; }

        public int H { get; protected set; }

        public bool HasPush { get; protected set; }

        public int LastDir { get; } = -1;

        private List<int> Cells;

        internal GameState()
        {
        }

        public GameState(Game game)
        {
            this.Depth = 1;
            this.Map = game.Map.ToArray();
            this.X = game.X;
            this.Y = game.Y;
            this.W = game.W;
            this.H = game.H;
            var cells = new List<int>();
            GetAllCells(X + Y * W, cells);
            this.Cells = cells;
        }
        public GameState(GameState game, int dir)
        {
            this.Map = game.Map.ToArray();
            this.LastState = game;
            this.X = game.X;
            this.Y = game.Y;
            this.W = game.W;
            this.H = game.H;
            this.LastDir = dir;
            this.Depth = game.Depth + 1;
            this.Cells = game.Cells;
        }
        /// <summary>
        /// 移动一步
        /// </summary>
        /// <param name="dir">方向：0左；1上；2右；3下</param>
        public GameState Move(int dir)
        {
            var state = new GameState(this, dir);
            int i = X + Y * W;
            int v = dir == 0 ? -1 : dir == 1 ? -W : dir == 2 ? 1 : W;
            if(state.Map[i + v] == 8)
            {
                return null;
            }
            if(state.Map[i + v] == 2 || state.Map[i + v] == 3)
            {
                if(state.Map[i + 2 * v] != 0 && state.Map[i + 2 * v] != 1)
                {
                    return null;
                }
                state.Map[i] = state.Map[i] == 5 ? 1 : 0;
                state.Map[i + v] = state.Map[i + v] == 3 ? 5 : 4;
                if(state.Map[i + 2 * v] == 1)
                    state.Map[i + 2 * v] = 3;
                else if(state.Map[i + 2 * v] == 0)
                    state.Map[i + 2 * v] = 2;
                state.HasPush = true;
            }
            else if(state.Map[i + v] == 0 || state.Map[i + v] == 1)
            {
                state.Map[i] = state.Map[i] == 5 ? 1 : 0;
                state.Map[i + v] = state.Map[i + v] == 1 ? 5 : 4;
            }
            else
            {
                return null;
            }
            state.X = (i + v) % W;
            state.Y = (i + v) / W;
            return state;
        }

        public bool Check()
        {
            return !this.Map.Any(x => x == 2);
        }

        public bool IsDeath()
        {
            if(!HasPush)
            {
                return false;
            }

            for(int i = 1; i < this.Map.Length; i++)
            {
                if(this.Map[i] == 2 && IsDeath(i))
                {
                    return true;
                }
            }

            //if(HasDeathAreas())
            //{
            //    return true;
            //}
            return false;
            //var boxs = Enumerable.Range(0, this.Map.Length).Where(x => IsBox(x)).ToList();
            //return boxs.All(IsDeath);
        }

        protected bool IsDeath(int i)
        {
            var _l = i - 1;
            var _u = i - W;
            var _d = i + W;
            var _r = i + 1;
            if(IsWall(_l) && IsWall(_u))
            {
                return true;
            }
            if(IsWall(_r) && IsWall(_u))
            {
                return true;
            }
            if(IsWall(_l) && IsWall(_d))
            {
                return true;
            }
            if(IsWall(_r) && IsWall(_d))
            {
                return true;
            }
            var _lu = i - 1 - W;
            var _ld = i - 1 + W;
            var _ru = i + 1 - W;
            var _rd = i + 1 + W;
            if(IsWallOrBox(_l) && IsWallOrBox(_u) && IsWallOrBox(_lu))
            {
                return true;
            }
            if(IsWallOrBox(_r) && IsWallOrBox(_u) && IsWallOrBox(_ru))
            {
                return true;
            }
            if(IsWallOrBox(_l) && IsWallOrBox(_d) && IsWallOrBox(_ld))
            {
                return true;
            }
            if(IsWallOrBox(_r) && IsWallOrBox(_d) && IsWallOrBox(_rd))
            {
                return true;
            }
            return false;
        }

        protected bool IsWallOrBox(int i)
        {
            return IsWall(i) || IsBox(i);
        }
        protected bool IsBox(int i)
        {
            return this.Map[i] == 2 || this.Map[i] == 3;
        }

        protected bool IsWall(int i)
        {
            return this.Map[i] == 8;
        }

        public virtual List<int> GetPaths()
        {
            var paths = new List<int>();
            var gs = this;
            while(gs != null && gs.LastDir > -1)
            {
                paths.Insert(0, gs.LastDir);
                gs = gs.LastState;
            }
            return paths.Any() ? paths : null;
        }

        public override string ToString()
        {
            return string.Join("", Map);
        }

        private void GetAllCells(int i, List<int> cells)
        {
            cells.Add(i);
            var list = new List<int>() { i };
            foreach(var i1 in list)
            {
                for(int dir = 0; dir < 4; dir++)
                {
                    int v = dir == 0 ? -1 : dir == 1 ? -W : dir == 2 ? 1 : W;
                    var t = i1 + v;
                    if(!cells.Contains(t) && !IsWall(t))
                    {
                        GetAllCells(t, cells);
                    }
                }
            }
        }
        private bool IsFreeCell(int i)
        {
            return this.Map[i] == 0 || this.Map[i] == 1 || this.Map[i] == 4 || this.Map[i] == 5;
        }

        private bool HasDeathAreas()
        {
            var freeArea = new List<int>();
            GetFreeCells(X + Y * W, freeArea);
            var others = this.Cells.Except(freeArea).Where(x => !IsBox(x)).ToList();
            if(others.Count == 0)
            {
                return false;
            }
            var area = new List<int>();
            var bs = new List<int>();
            var ts = new List<int>();
            while(others.Any())
            {
                var item = others.First();
                area.Clear();
                bs.Clear();
                ts.Clear();
                GetUnreachableArea(item, area, bs, ts);
                if(area.Count < 6 && bs.Count < 3)
                {
                    if(bs.Count != ts.Count)
                    {
                        return true;
                    }
                }
                others = others.Except(area).ToList();
            }
            return false;
        }
        private void GetFreeCells(int i, List<int> cells)
        {
            cells.Add(i);
            var list = new List<int>() { i };
            foreach(var i1 in list)
            {
                for(int dir = 0; dir < 4; dir++)
                {
                    int v = dir == 0 ? -1 : dir == 1 ? -W : dir == 2 ? 1 : W;
                    var t = i1 + v;
                    if(!cells.Contains(t) && IsFreeCell(t))
                    {
                        GetFreeCells(t, cells);
                    }
                }
            }
        }


        private void GetUnreachableArea(int i, List<int> area, List<int> bs, List<int> ts)
        {
            area.Add(i);
            var list = new List<int>() { i };
            foreach(var i1 in list)
            {
                for(int dir = 0; dir < 4; dir++)
                {
                    int v = dir == 0 ? -1 : dir == 1 ? -W : dir == 2 ? 1 : W;
                    var t = i1 + v;
                    if(this.Map[t] == 1 && !ts.Contains(t))
                    {
                        ts.Add(t);
                    }
                    if(this.Map[t] == 2 && !bs.Contains(t))
                    {
                        bs.Add(t);
                    }
                    if(!area.Contains(t) && this.Map[t] < 2)
                    {
                        GetUnreachableArea(t, area, bs, ts);
                    }
                }
            }
        }
    }
}